//【案例开放009】1023上机编程“备忘录设计系统”学习交流
// http://3ms.huawei.com/km/groups/3803117/blogs/details/9241119
//案例开放009】1023上机编程“备忘录设计系统”学习交流
//日期：2020-10-30 16:08浏览：11600回复：302025-12-26 失效
//【案例开放009】1023上机编程“备忘录设计系统”学习交流
// 1.  题目
//今天学习1023上机编程工作级第3题_专业级第1题。题目：备忘录设计系统
//请设计一个备忘录系统，要求有以下功能：
//·     addEvent(int startDate, String content, int num, int period) – 自日期
// startDate 开始（startDate 包含在内）， 添加 num 个以 period
// 为间隔周期待办事项 content。例如若命令为 addEvent(0,"a",4,2)，表示于日期
// 0，2，4，6 分别添加待办事项 "a"。 o
// 返回本次操作共计新增待办事项的数量。若部分日期上已存在该事项，无论该事项是否设置为已完成，这些日期不需添加该事项。
//·     finishEvent(int date, String content) – 将日期 date 上的 content
//事项设置为已完成。 o  若该日期上不存在此事项，或该日期上此事项已完成，返回
// false； o  若设置操作完成，则返回 true。 ·     removeEvent(int date, String
// content) – 移除日期 date 上的 content 事项。 o  若该日期上不存在此事项，返回
// false； o  若移除操作完成，则返回 true。 ·     queryTodo(int startDate, int
// endDate) – 查询从 startDate 到 endDate（起止日期均包含在内）
//这段日期内所有的未完成的 content
//事项，并将查询到的事项以字符串形式按日期升序记于数组后返回，若查询到相同日期的多条待办事项，则将其按字典序排列。
//示例 1：
//输入：["MemoSystem","addEvent","queryTodo","finishEvent","removeEvent"]
//[[],[2,"eat a burger",2,3],[0,5],[2,"eat a burger"],[2,"eat a burger"]]
//输出：[null,2,["eat a burger","eat a burger"],true,true]
//解释：
// MemoSystem ms = MemoSystem();
// ms.addEvent(2,"eat a burger",2,3); // 自日期 2 开始，添加 2 个间隔周期为 3
// 的待办事项 "eat a burger"， 即在日期 2、5 添加该待办事项。本次操作共新添加了
// 2
//个待办事项，返回 2 ms.queryTodo(0,5); //查询自日期 0 至日期 5
// 的所有未完成的事项，返回数组 ["eat a burger","eat a burger"]
// ms.finishEvent(2,"eat a burger"); // 将系统中日期为 2 的待办事项 "eat a
// burger" 设置为已完成，返回 true ms.removeEvent(2,"eat a burger"); //
// 移除系统中日期为 2 的事项 "eat a burger"，返回 true 注：输出中的 null
//表示此对应函数无输出（其中：C 的构造函数有返回值，但是也是无需输出） 示例 2：
//输入：
//["MemoSystem","addEvent","addEvent","removeEvent","finishEvent","addEvent","addEvent","queryTodo","queryTodo","finishEvent","addEvent"]
//[[],[2,"save files",1,1],[2,"eat a burger",1,1],[2,"drink water"],[1,"drink
// water"],[0,"eat a burger",5,2],[2,"save files",1,1],[0,4],[10,11],[2,"eat a
// burger"],[2,"eat a burger",1,1]] 输出：[null,1,1,false,false,4,0,["eat a
// burger","eat a burger","save files","eat a burger"],[],true,0] 解释：
// MemoSystem ms = MemoSystem();
//第 3 个命令 ms.addEvent(2,"eat a burger",1,1); //
//同一个日期可以增加不同的待办事项，本次操作共新添加了 1 个待办事项，返回 1 第 6
//个命令 ms.addEvent(0,"eat a burger",5,2); // 自日期 0 开始，添加 5
//个间隔周期为 2 的待办事项 "eat a burger"， 即在日期 0，2，4，6，8
//添加该待办事项。由于日期 2 的记录中已存在该事项，因此本次操作共新添加了 4
//个待办事项，返回 4 第 8 个命令 ms.queryTodo(0,4); // 查询自日期 0 至日期 4
//的所有未完成的事项，按日期返回，其中日期 2 的待办事项需按字典序排列， 返回数组
//["eat a burger","eat a burger","save files","eat a burger"] 第 9 个命令
// ms.queryTodo(10,11); // 查询自日期 10 至日期 11
// 的所有未完成的事项，返回空数组
//[] 注：输出中的 null 表示此对应函数无输出（其中：C
//的构造函数有返回值，但是也是无需输出） 提示： 1 <=
// addEvent,finishEvent,removeEvent,queryTodo 总操作数 <= 1000 0 <= startDate <=
// endDate <= 1000 0 < num, period, 0 <= startDate + (num - 1) * period <= 1000
// 1 <= content.length <= 20 ，仅包含小写字母、大写字母与空格
// 0 <= date <= 1000
//·     queryTodo 函数对于 Java/Js/Python/Go
//语言，如果返回的记录为空，则返回空数组
// 2.  题目分析
//题目理解：
//日期和事务的对应关系，可以用下面这张图表示：
//也可以用下面这张表来表示：
//日期
//事务名称
//完成状态
// 1
//事务1
//未完成
// 1
//事务2
//完成
// 2
//事务1
//未完成
// n
//事务n
//...
//注意日期只是一个整数，范围是[0,1000]
//题目有提示总操作数 <= 1000，所以每天的事务数量最多也是1000。
//解题思路：
//这是典型的增删改查设计题，日常工作中经常遇到类似的场景。
//数据结构：数组/hash/链表均可以，这题主要考察基本编程功底，解法较多。
//类似题目：【案例开放003】0814可信上机编程工作级第3题/专业级第1题-招标系统
// http://3ms.huawei.com/km/groups/3803117/blogs/details/8770495?l=zh-cn
//常见的思路是采用分层设计的方法，先建立日期ID和某天待办事务集合的映射关系，再处理某天待办事务的状态即可。
//注意queryTodo需要先按日期排序、同一个日期内要按待办事项的字典序排列，不要理解成整体按字典序排列。
//员工4-C++代码：44行、最大圈复杂度4，两层map
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

class MemoSystem {
 public:
  MemoSystem() {}
  int AddEvent(int startDate, string content, int num, int period) {
    int count = 0;
    for (int i = startDate; i < startDate + num * period; i += period) {
      if (memoMap[i].find(content) == memoMap[i].end()) {
        memoMap[i][content] = false;
        ++count;
      }
    }
    return count;
  }
  bool FinishEvent(int date, string content) {
    if (memoMap[date].find(content) != memoMap[date].end() &&
        memoMap[date][content] == false) {
      memoMap[date][content] = true;
      return true;
    }
    return false;
  }
  bool RemoveEvent(int date, string content) {
    if (memoMap[date].find(content) != memoMap[date].end()) {
      memoMap[date].erase(content);
      return true;
    }
    return false;
  }
  vector<string> QueryTodo(int startDate, int endDate) {
    vector<string> items;
    for (int i = startDate; i <= endDate; ++i) {
      for (auto &item : memoMap[i]) {
        if (!item.second) {
          items.emplace_back(item.first);
        }
      }
    }
    return items;
  }
  unordered_map<int, map<string, bool>> memoMap;
};
